package dmsxl.lianbiao;

/**
 * Author: Zhang Dongwei
 * Date: 2023/4/7 15:16
 */
public class lb2_707 {
    public static void main(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.addAtHead(1);
        myLinkedList.addAtTail(3);
        myLinkedList.addAtIndex(1, 2);    // 链表变为 1->2->3
        myLinkedList.get(1);              // 返回 2
        myLinkedList.deleteAtIndex(1);    // 现在，链表变为 1->3
        myLinkedList.get(1);              // 返回 3
    }
}

// 单链表
//class MyLinkedList {
//
//    int size;
//    ListNode head;
//
//    public MyLinkedList() {
//        size = 0;
//        head = new ListNode(0);
//    }
//
//    public int get(int index) {
//        if (index <0 || index >= size){
//            return -1;
//        }
//        ListNode cur = head;
//        for (int i = 0; i <= index; i++){
//            cur = cur.next;
//        }
//        return cur.val;
//    }
//
//    public void addAtHead(int val) {
//        addAtIndex(0 ,val);
//    }
//
//    public void addAtTail(int val) {
//        addAtIndex(size, val);
//    }
//
//    public void addAtIndex(int index, int val) {
//        if (index > size){
//            return;
//        }
//        index = Math.max(0, index);
//        size ++;
//        ListNode pre = head;
//        for (int i = 0; i < index; i++){
//            pre = pre.next;
//        }
//        ListNode toAdd = new ListNode(val);
//        toAdd.next = pre.next;
//        pre.next = toAdd;
//    }
//
//    public void deleteAtIndex(int index) {
//        if (index < 0 || index >= size) return;
//        size --;
//        ListNode pre = head;
//        for (int i = 0; i < index; i++){
//            pre = pre.next;
//        }
//        pre.next = pre.next.next;
//    }
//}

//双链表(不好想)
class MyLinkedList {
    int size;
    DListNode head;
    DListNode tail;

    public MyLinkedList() {
        size = 0;
        head = new DListNode(0);
        tail = new DListNode(0);
        head.next = tail;
        tail.prev = head;
    }

    public int get(int index) {
        if (index < 0 || index >= size) {
            return -1;
        }
        DListNode curr;
        if (index + 1 < size - index) {
            curr = head;
            for (int i = 0; i <= index; i++) {
                curr = curr.next;
            }
        } else {
            curr = tail;
            for (int i = 0; i < size - index; i++) {
                curr = curr.prev;
            }
        }
        return curr.val;
    }

    public void addAtHead(int val) {
        addAtIndex(0, val);
    }

    public void addAtTail(int val) {
        addAtIndex(size, val);
    }

    public void addAtIndex(int index, int val) {
        if (index > size) {
            return;
        }
        index = Math.max(0, index);
        DListNode pred, succ;
        if (index < size - index) {
            pred = head;
            for (int i = 0; i < index; i++) {
                pred = pred.next;
            }
            succ = pred.next;
        } else {
            succ = tail;
            for (int i = 0; i < size - index; i++) {
                succ = succ.prev;
            }
            pred = succ.prev;
        }
        size++;
        DListNode toAdd = new DListNode(val);
        toAdd.prev = pred;
        toAdd.next = succ;
        pred.next = toAdd;
        succ.prev = toAdd;
    }

    public void deleteAtIndex(int index) {
        if (index < 0 || index >= size) {
            return;
        }
        DListNode pred, succ;
        if (index < size - index) {
            pred = head;
            for (int i = 0; i < index; i++) {
                pred = pred.next;
            }
            succ = pred.next.next;
        } else {
            succ = tail;
            for (int i = 0; i < size - index - 1; i++) {
                succ = succ.prev;
            }
            pred = succ.prev.prev;
        }
        size--;
        pred.next = succ;
        succ.prev = pred;
    }
}